home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 09 - 1993 / 09.08 Aug 93 / Programmers' Challenge / findCity.c < prev   
Encoding:
C/C++ Source or Header  |  1994-11-06  |  4.0 KB  |  180 lines  |  [TEXT/KAHL]
  1. /* FindCity by Bob Boonstra */
  2.  
  3. #define kMax        5
  4. #define kSentinal    0x035A5A5A
  5. #define low3Bytes    0x00FFFFFF
  6.  
  7. typedef struct distRec {
  8.     short            theDist;
  9.     unsigned short    theIndx;
  10. } distRec;
  11.  
  12. Boolean FindCity(cityNames, cityToFindNamePtr, closestMatches)
  13. Str255        cityNames[];
  14. Str255        *cityToFindNamePtr;
  15. unsigned short closestMatches[];
  16. {
  17.     distRec            theRec[kMax];
  18.     unsigned char    *curCityP, *city2Find;
  19.     unsigned short    curIndx;
  20.     register short    maxDist;
  21.      
  22.     city2Find = *cityToFindNamePtr;
  23.     curCityP = cityNames[0];
  24.     /*
  25.      *    Scan for an exact match.
  26.      */
  27.     {
  28.         register long    toFind3;
  29.  
  30.         curIndx = 0;
  31.         toFind3 = *(long *)city2Find & low3Bytes;
  32.         do {
  33.             if ( *(long *)curCityP == *(long *)city2Find ) {
  34.     /*
  35.      *    If first 4 characters match, look at the
  36.      *    rest in chunks of 4 characters.
  37.      */
  38.                 register short charsLeft;
  39.                 register unsigned char *s1 = curCityP+4;
  40.                 register unsigned char *s2 = city2Find+4;
  41.  
  42.                 if ( (charsLeft = *curCityP-7) >= 0 ) {
  43.                     do {
  44.                         if ( *(long *)s1 != *(long *)s2 )
  45.                             goto nextOne;
  46.                         s1 += 4;  s2 += 4;
  47.                     } while ( (charsLeft-=4) >= 0 );
  48.                 }
  49.     /*
  50.      *    If all chunks of 4 characters match, look at the
  51.      *    rest individually.
  52.      */
  53.                 if (charsLeft+=4) {
  54.                     do {
  55.                         if (*s1++ != *s2++)
  56.                             goto nextOne;
  57.                     } while (--charsLeft);
  58.                 }
  59.     /*
  60.      *    Exact match found.  Return index of match.
  61.      */
  62.                 closestMatches[0] = curIndx;
  63.                 return(1);
  64.     /*
  65.      *    Process the next city. Exit if it is greater in
  66.      *    alphabetic order (based on 1st 3 characters,
  67.      *    w/o length byte).
  68.      *    Sentinal will force exit if necessary.
  69.      */
  70.             nextOne: ;
  71.             }
  72.  
  73.             ++curIndx;
  74.             curCityP+=sizeof(Str255);
  75.  
  76.         }  while ( (*(long *)curCityP & low3Bytes) <= toFind3 );
  77.     }
  78.     /*
  79.      *    Initialize distance structure for 5 closest matches.
  80.      */
  81.     noMatch:
  82.     {
  83.         register distRec *p = &theRec[0];
  84.  
  85.         (++p)->theDist = (++p)->theDist = (++p)->theDist =
  86.             (++p)->theDist = (p)->theDist = maxDist = 255;
  87.     }
  88.     /*
  89.      *    Loop thru cityNames to find closest matches.
  90.      */
  91.     curCityP=cityNames[0];
  92.     curIndx=0;
  93.     do {
  94.         register short curDist;
  95.     /*
  96.      *    Calculate dist between cityToFind and cityName[curIndx].
  97.      */
  98.         {
  99.             register unsigned char *s1,*s2;
  100.             register short lng;
  101.  
  102.     /*    initialize dist to length difference */
  103.             s2 = city2Find;
  104.             lng = *s2++;
  105.             if ((curDist = *(s1=curCityP) - lng) < 0) {
  106.                 curDist = -curDist;
  107.                 lng = *s1;
  108.             }
  109.     /*
  110.      *    Move to next city if distance exceeds the distance
  111.      *    of 5 other cities.
  112.      *    Increment dist for each nonMatching char.
  113.      *    Unroll for a little extra speed.
  114.      */
  115.             ++s1;
  116.             do {
  117.                 if (*s1++ != *s2++)
  118.                     if (++curDist >= maxDist) goto nextCity;
  119.                 if (!(--lng)) break;
  120.                 if (*s1++ != *s2++)
  121.                     if (++curDist >= maxDist) goto nextCity;
  122.                 if (!(--lng)) break;
  123.                 if (*s1++ != *s2++)
  124.                     if (++curDist >= maxDist) goto nextCity;
  125.                 if (!(--lng)) break;
  126.                     if (*s1++ != *s2++)
  127.                 if (++curDist >= maxDist) goto nextCity;
  128.             } while (--lng);
  129.         }
  130.     /*
  131.      *    This city is closer than at least one of the five
  132.      *    currently closest cities.  Store the distance and
  133.      *    the index in the proper place.
  134.      *    distRec[0].theIndx is the closest match, and
  135.      *    distRec[0].theDist is the associated distance
  136.      */
  137.     {
  138.         register distRec *q=theRec+kMax-1;
  139.  
  140.         maxDist=curDist;
  141.         if (curDist >= (q-1)->theDist) goto storeIt;
  142.         *q = *(q-1);
  143.         maxDist = q->theDist;  --q;  /* [3]-->[4] */
  144.         if (curDist >= (q-1)->theDist) goto storeIt;
  145.         *q = *(q-1);  --q;           /* [2]-->[3] */
  146.         if (curDist >= (q-1)->theDist) goto storeIt;
  147.         *q = *(q-1);  --q;           /* [1]-->[2] */
  148.         if (curDist >= (q-1)->theDist) goto storeIt;
  149.         *q = *(q-1);  --q;           /* [0]-->[1] */
  150.     storeIt:
  151.         q->theDist = curDist;
  152.         q->theIndx = curIndx;
  153.     }
  154.     /*
  155.      *    Process next city.
  156.      */
  157.     nextCity:
  158.         curCityP+=sizeof(Str255);
  159.         ++curIndx;
  160.     /*
  161.      *    Exit when sentinal is found.
  162.      */
  163.     } while (*(long *)curCityP != kSentinal);
  164.  
  165.     /*
  166.      *    Return indices of 5 closest cities.
  167.      */
  168.     {
  169.         register unsigned short *p = closestMatches;
  170.         register unsigned short *q = &theRec[0].theIndx;
  171.  
  172.         *p++ = *q;  q+=2;
  173.         *p++ = *q;  q+=2;
  174.         *p++ = *q;  q+=2;
  175.         *p++ = *q;  q+=2;
  176.         *p   = *q;
  177.     }
  178.     return(0);
  179. }
  180.